|
KMID : 0380319920500000031
|
|
Journal of Korean Research Institute for Better Living
1992 Volume.50 No. 0 p.31 ~ p.44
|
|
|
An Algorithm for the Shape Construction of a Dot Pattern Using L_1-metric
|
|
|
|
|
Abstract
|
|
|
|
In this paper the problem of constructing the shape of a dot pattern (consisting of a set S of n points in the plane) using L_1-metric, so-called an α_1-shape of S, is considered and an O(nlogn)-time algorithm of constructing the α_1-shape is presented. For a given real value α_1, a point p in S is termed as the α_1-extreme of S if there exists a closed L_1-circle of radius l/α_1 such that p lies on its boundary and it contains all points of S. If, for two α_1-extreme points p and q there exists a closed L_1-circle of radius l/α_1 with both points on its boundary and it contains all other points, then p and q are said to be an α_1-neighbor of each other. The α_1-shape of S is the rectilinear line graph whose vertices are the α_1-extreme points and whose edges are connected with all α_1-neighbors.
|
|
|
KEYWORD
|
|
|
|
|
|
FullTexts / Linksout information
|
|
|
|
|
|
Listed journal information
|
|
|
|